|
In queueing theory, a discipline within the mathematical theory of probability, Burke's theorem (sometimes the Burke's output theorem) is a theorem (stated and demonstrated by Paul J. Burke while working at Bell Telephone Laboratories) asserting that, for the M/M/1 queue, M/M/c queue or M/M/∞ queue in the steady state with arrivals a Poisson process with rate parameter λ: # The departure process is a Poisson process with rate parameter λ. # At time ''t'' the number of customers in the queue is independent of the departure process prior to time ''t''. ==Proof== Burke first published this theorem along with a proof in 1956. The theorem was anticipated but not proved by O’Brien (1954) and Morse (1955). A second proof of the theorem follows from a more general result published by Reich. The proof offered by Burke shows that the time intervals between successive departures are independently and exponentially distributed with parameter equal to the arrival rate parameter, from which the result follows. An alternative proof is possible by considering the reversed process and noting that the M/M/1 queue is a reversible stochastic process.〔 Consider the figure. By Kolmogorov's criterion for reversibility, any birth-death process is a reversible Markov chain. Note that the arrival instants in the forward Markov chain are the departure instants of the reversed Markov chain. Thus the departure process is a Poisson process of rate λ. Moreover, in the forward process the arrival at time t is independent of the number of customers after t. Thus in the reversed process, the number of customers in the queue is independent of the departure process prior to time ''t''. This proof could be counter-intuitive, in the sense that the departure process of a birth-death process is independent of the service offered. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Burke's theorem」の詳細全文を読む スポンサード リンク
|